
#include <iostream>
#include <vector>

void printArr(const std::vector<int>& arr)
{
    for(auto e : arr)
        printf("%d ", e);
    printf("\n");
}

/*随机返回数组arr[left, right]之间的某个数*/
int _getRandomKey(const std::vector<int>& arr, int left, int right)
{
    int r = rand();
    return arr[left + r % (right - left + 1)];
}

/*对数组arr的区间[left, right]进行快速排序*/
void _qsort(std::vector<int>& arr, int left, int right)
{
    // 0.递归出口
    if(left >= right) return;

    // 1.将数组分成三块：左边比key小，右边比key大 [left, l] [l+1, r-1] [r, right]
    int key = _getRandomKey(arr, left, right); // 1.1找key
    int i = left, l = left-1, r = right+1; //l指向左区间的最后一个，r指向右区间的第一个，i是去扫描的
    while(i < r)
        if(arr[i] < key) //小于key，往左区间换
            std::swap(arr[i++], arr[++l]);
        else if(arr[i] > key) //大于key，往右区间
            std::swap(arr[i], arr[--r]);
        else
            ++i;
            
    // 2.对左右区间进行递归
    _qsort(arr, left, l);
    _qsort(arr, r, right);
}

/*对数组arr进行快速排序*/
void qsort(std::vector<int>& arr)
{
    srand(time(NULL));
    _qsort(arr, 0, arr.size()-1);
}

int main()
{
    std::vector<int> a = {-1, 0, 4, 2, 9, 5, 7, 3, 1, 7, 8, -2};
    printArr(a);
    qsort(a);    
    printArr(a);
    return 0;
}